#include <iostream>
using namespace std;
struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;
};
BiTNode *T;
void preOrderTraveral(BiTNode* &T);
void Inorder(BiTNode* &T);
void Posorder(BiTNode* &T);
void CreateBiTree(BiTNode* &T){
	char ch;
	if((ch=getchar())=='#')T = NULL;
		else{
		T = new BiTNode;
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}
/***************
		A
	B		C
D				E
	F		G
输入：ABD#F###C#EG###创造一个树! 
前序构造的树 
****************/

int main(){
	cout<<"创建一棵树，其中A->Z字符代表树的数据，用“#”代表空树："<<endl; 
	CreateBiTree(T);
	cout<<"先序遍历"<<endl;
	preOrderTraveral(T);
	cout<<endl;
	cout<<"中序遍历"<<endl;
	Inorder(T); 
	cout<<endl;
	cout<<"后序遍历"<<endl;
	Posorder(T);
	return 1;
} 
/*******

*******/ 
void preOrderTraveral(BiTNode* &T){
	if(T){
		cout<<T->data;
		preOrderTraveral(T->lchild);
		preOrderTraveral(T->rchild);
	}else{
		cout<<"";
	}
}
void Inorder(BiTNode* &T){
	if(T){
		Inorder(T->lchild);
		cout<<T->data;
		Inorder(T->rchild);
	}else{
		cout<<"";	
	} 
}

void Posorder(BiTNode* &T){
	if(T){
		Posorder(T->lchild);
		Posorder(T->rchild);
		cout<<T->data;
	}else{
		cout<<"";	
	} 
}
